package q921_minAddToMakeValid;

public class Solution {
    /*
    使括号有效的最少添加
    直接使用贪心 遇到)时 考察当前cnt是否大于0 如果不是 则说明要补(
    否则cnt--
    最后查看cnt是否大于0 如果是 说明要补)
     */
    public int minAddToMakeValid(String s) {
        int ans = 0, cnt = 0;
        for (int i = 0; i < s.length(); ++i) {
            char c = s.charAt(i);
            if (c == ')') {
                if (cnt <= 0) ans++;
                else --cnt;
            } else {
                cnt++;
            }
        }
        return ans + cnt;
    }
}
